The present invention relates to a technology suitably applied to data processors having a residue calculation function and more particularly to a technology suitably applied to encoders and decoders using residue multiplication and power-residue calculations.
Cryptography technology includes public-key cryptography. For example, as shown in FIG. 14, a sender encodes a message M according to "C=M.sup.e mod N" to make a cryptogram C, and the receiver decodes the cryptogram C according to "M=C.sup.d mod N" to obtain the message M. In the above encoding, the parameters e and N are made public. In the decoding, d is kept secret. The operation expressions used for the encoding and decoding are for power-residue operations, and representatively "X.sup.Y mod N" (where X, Y and N are positive integers). "mod" means a residue operation and the power-residue operation "X.sup.Y mod N" has a solution which is the remainder of the division of X.sup.Y by N.
It is generally known that the encoder/decoder can offer a high degree of security by using a power-residue operation "X.sup.Y mod N" (where X, Y and N are positive integers). A description of this fact is found in the "Modern Cryptography Theory" by Ikeno and Koyama, edited by the Institute of Electronics, Information and Communication Engineers of Japan (1986).
Because X, Y and N are very large numbers ranging from 100 to 2,000 bits, it has been a problem in the mathematics and engineering fields how to calculate "X.sup.Y mod N" at high speed.
As one of the solutions of this problem, algorithm 1! shown below is a classically known.
Algorithm
______________________________________ input X, Y = e.sub.n e.sub.n-1 . . . e.sub.1, N Step 1 A = X Step 2 B = X Step 3 for i = n-1 to 1 step -1 { Step 4 A = A.sup.2 mod N Step 5 if e.sub.i = 1 then A = A.multidot.B mod N Step 6 } Step 7 output A Step 8 ______________________________________
In this algorithm, n corresponds to the number of bits Y, and e.sub.n e.sub.n-1 . . . e.sub.1 is a binary representation of Y. This algorithm, roughly speaking, is executed by combining a square-residue multiplication "A.sup.2 mod N" (step 5) and a residue multiplication "A.multidot.B mod N" (step 6). Letting the number of logical value 1 in e.sub.n e.sub.n-1 . . . e.sub.1 be represented by r(e), the square-residue multiplication "A.sup.2 mod N" is repetitively performed n-1 times and the residue multiplication "A.multidot.B mod N" is repeated r(e)-1 times.
Because in the Algorithm 1! the power-residue operation "X.sup.Y mod N" is resolved into the residue multiplication "A.multidot.B mod N" and so forth, an arithmetic unit capable of realizing the calculation function of "A.multidot.B mod N" is obtained.
There is a problem, however, that because A and B are both large numbers having their data lengths of, for example, 512 bits, the interim result AB becomes a large 1024-bit number. Further, because the final result is the remainder of the division of A.multidot.B by N, the division 1024-bit number.div.a 512-bit number, involving very large values, must be performed. Although the multiplication can be parallelly executed at high speed using a microprocessor by dividing the multiplier and the multiplicand, division is difficult to be parallelly processed at high speed. Even if the calculation is resolved into the residue multiplication operations "A.multidot.B mod N" for execution, the division in these residue multiplication calculations still prevents higher speed processing.
For solving the problem of division in the above residue multiplication "A.multidot.B mod N" in particular, the following Algorithm 2! is known which does not perform the division by N in executing the residue multiplication "A.multidot.B.multidot.R.sup.-1 mod N", where R is 2.sup.n (n is the size of N for example) and a positive integer satisfying R&gt;N.
The proof leading to the Algorithm 2! that executes the residue multiplication "A.multidot.B.multidot.R.sup.-1 mod N" without performing division by N will not be described in detail. But there is a description in, for example, Montgomery, P. L.: Modular Multiplication without Trial Division, Mathematics of Computation, Vol. 44, No. 170, pp. 519-521 (1985), Dusse, S. R. and Kaliski, B. S. Jr.: A Cryptographic Library for the Motorola DSP56000, Advances in Cryptology-EUROCRYPTO'90, Lecture Notes in Computer Science 473, pp. 230-244, Springer-Verlag (1991).
Algorithm 2! EQU N'=-N.sup.-1 mod R Step 1 EQU M=A.multidot.B.multidot.N' mod R Step 2 EQU t=(A.multidot.B+M.multidot.N)/R Step 3 EQU if t.gtoreq.N then return t-N else return t Step 4